The main entrance is at Uwinka on the main Cyangugu - Huye road. It's about 55km from Cyangugu and 90km from Huye. The road is mostly in good condition. There are regular buses along the route and hitching is also an option. Buses are often full when the reach here so if you're getting a bus out it may be best to try and book your ticket in advance.
If travelling from Cyangugu ignore the sign in town that says it's 20km and further ignore the sign 15km from Cyangugu directing you right up a dirt track. These refer to a small off shoot of the park, not the park proper.
